package leetcode_500;

import java.util.ArrayList;
import java.util.List;

/**
 * FindAllAnagramsInAString_438 寻找给定两个串 s,p 寻找s中所有连续子串 是p的混乱串
 * 2018年8月18日 下午1:33:01
 * @author 周杨
 * describe :用滑动窗口法  AC 94%
 */
public class FindAllAnagramsInAString_438 {
	/**
	 * 2018年8月18日 下午1:30:07
	 * @author 周杨
	 * describe :暴力解  每次判断子串是否符合 AC 8%
	 */
	public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res=new ArrayList<Integer>();
        for(int i=0;i<=s.length()-p.length();++i){
        	if(help(s,p,i))
        		res.add(i);
        }
        return res;
    }
	
	
	public boolean help(String s1,String s2,int index){
		int hash[]=new int[26];
		for(int i=0;i<s2.length();++i){
			hash[s2.charAt(i)-'a']++;
		}
		for(int j=0;j<s2.length();++j){
			int now=s1.charAt(j+index)-'a';
			if(hash[now]==0)
				return false;
			else 
				--hash[now];
		}
		return true;
	}
	
	/**
	 * 2018年8月18日 下午1:32:30
	 * @author 周杨
	 * describe :滑动窗口法 用双指针map AC 94%
	 */
	public List<Integer> findAnagrams1(String s, String p) {
		ArrayList<Integer> result = new ArrayList<>();
        if(s == null || p == null) return result;
        int left = 0,right =0,count = p.length();
        int[] map = new int[256];
        char[] sc = s.toCharArray();
        for (char c : p.toCharArray()) map[c] ++;
        while (right < s.length()) {
            if (map[sc[right++]]-->=1) count --;
            if (count == 0) result.add(left);
            if (right - left == p.length() && map[sc[left++]]++ >=0) count++;
        }
        return result;
    }
}

